# -*- encoding: utf-8 -*-
from DataStructures.LinkedList.doubly_linked_list import LinkedList


def LRU(x, obj=None):
    """
    LRU（leaset Recently Used）：最近最少使用策略，利用双向链表实现
    1. 如果数据已经存在链表中，遍历链表找到数据，将数据从原来的位置删除，重新插入表头
    2. 如果数据不再缓存链表中：
        - 如果链表未满，则直接加入链表头
        - 如果链表已满，删除尾部数据，将数据加入到链表头
    """
    max_len = 10
    if obj is None:
        obj = LinkedList()
    current = obj.head
    while current:
        if current.value == x:
            obj.delete(x)
            break
        current = current.next
    if current:
        obj.insert_head(x)
    else:
        if obj.len() >= max_len:
            obj.delete_tail()
        obj.insert_head(x)
    obj.display()
    return obj


if __name__ == '__main__':
    obj = LinkedList()
    obj = LRU(1, obj)
    obj = LRU(3, obj)
    obj = LRU(10, obj)
    obj = LRU(15, obj)
    obj = LRU(3, obj)
    obj = LRU(2, obj)
    obj = LRU(4, obj)
    obj = LRU(6, obj)
    obj = LRU(7, obj)
    obj = LRU(8, obj)
    obj = LRU(9, obj)
    obj = LRU(11, obj)






